package q16_threeSumClosest;

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        System.out.println(threeSumClosest(new int[]{-1,2,1,-4},1));
    }

    public static int threeSumClosest(int[] nums, int target) {
        // 先排序
        Arrays.sort(nums);
        int len = nums.length;
        // 如果最左边的三个数加起来比target大，或者最右边的三个数加起来比target小，就不用循环直接得到结果
        if(nums[0]+nums[1]+nums[2] >= target){
            return nums[0]+nums[1]+nums[2];
        }else if(nums[len - 1]+nums[len - 2]+nums[len - 3] <= target){
            return nums[len - 1]+nums[len - 2]+nums[len - 3];
        }
        // 设置一个初始返回值与差值初始值
        int res = nums[0] + nums[1] + nums[len - 1];
        int gap = target - res;
        for (int i = 0; i < len; i++) {

            if((i != 0)&&(nums[i] == nums[i - 1])){
                continue;
            }

            int p2 = i + 1;
            int p3 = len - 1;

            while(p2 < p3){
                int NewGap = target - (nums[i] + nums[p2] + nums[p3]);

                boolean b = Math.abs(NewGap) > Math.abs(gap);
                if (NewGap == 0) {
                    return nums[i] + nums[p2] + nums[p3];
                }
                if((NewGap < 0) && b){
                    p3--;
                }else if((NewGap > 0) && b){
                    p2++;
                }else if((NewGap < 0)){
                    res = nums[i] + nums[p2] + nums[p3];
                    gap = NewGap;
                    p3--;
                }else{
                    res = nums[i] + nums[p2] + nums[p3];
                    gap = NewGap;
                    p2++;
                }
            }
        }

        return res;
    }
}
